100

however, this has been in vain. The list of failures or, in some cases, highly intelligent

attempts to solve the problem is quite exciting to read. Even clearer and more exciting are

the articles by Scott Aaranson (2003, 2005), which show quite amusingly what one can

learn here about computers and complex problems. However, another aspect is perhaps

even more fascinating: limitations of decisions, but especially formally exact computer-

based decisions. This is masterfully illustrated in an article by Chaitin (2006), and the

relations to Turing computability are also made well clear. The important point here is that

humans, as thinking, feeling, and evaluating creatures, can obviously still make decisions

that a computer, or more generally a Turing machine, can no longer make (see Chaps. 14

and 16). The Turing Award is the highest award for computer science. Laureates such as

Martin Hellmann (pretty-good-privacy-encryption of e-mails) show that they are fully

aware of this human responsibility (https://nuclearrisk.org; see Chap. 16).

Conclusion

• Alan Turing has generally reproduced all computable problems with the help of

the Turing machine. All non-Turing computable problems cannot be solved by

computers and remain tasks for humans. The question of when a bioinformatics

problem will be completed is difficult to answer for problems with built-in

combinatorics.

• Unfortunately, many particularly interesting problems in bioinformatics are NP

(nondeterministic polynomial complexity) problems, for example, protein struc­

ture prediction as well as most network computations (e.g., the traveling sales­

man problem: How does he optimally plan his city route?). Computer clusters are

needed for processing large omics datasets and in modeling genome-wide meta­

bolic networks, but also for modeling complex signaling cascades, for ab initio

protein folding simulations, and for complex image processing (e.g., 3-D tomo­

grams, deep learning), as well as for large in silico drug screens and molecular

dynamics simulations.

• In general, more powerful computers, the bundling of many computer nodes (par­

allelisation) and application-specific chips can also directly increase computer

performance. In addition, the search for faster heuristics and new, clever algo­

rithm strategies and procedures is a current task in bioinformatics, since the data

are rapidly becoming more and more complex. Simpler problems (P-problems),

on the other hand, require very manageable computing time, for example all

sequence analyses, because a database search or query only grows linearly with

the size of the database and the length of the query sequence, i.e. quadratically

overall (quadratic polynomial problem P), as do predictions on RNA folding.

8  When Does the Computer Stop Calculating?